package leetcode._07_贪心;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.IntStream;

/**
 * @author pppppp
 * @date 2022/3/20 15:47
 * 给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
 * <p>
 * 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
 * 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
 * 以这种方式修改数组后，返回数组 可能的最大和 。
 * 示例 1：
 * 输入：nums = [4,2,3], k = 1
 * 输出：5
 * 解释：选择下标 1 ，nums 变为 [4,-2,3] 。
 * <p>
 * 示例 2：
 * 输入：nums = [3,-1,0,2], k = 3
 * 输出：6
 * 解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。
 * <p>
 * 示例 3：
 * 输入：nums = [2,-3,-1,5,-4], k = 2
 * 输出：13
 * 解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。
 */
public class _1005_K次取反后最大化的数组和 {

    /*1.代码随想录 贪心思维*/
    public int largestSumAfterKNegations_1(int[] nums, int K) {
        Integer[] arr = {1,5,8,4,2,6,4};
        Arrays.sort(arr, (o1, o2) -> {
            return o2 - o1;
        });
        // 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
        nums = IntStream.of(nums)
                .boxed()
                .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
                .mapToInt(Integer::intValue).toArray();
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            //从前向后遍历，遇到负数将其变为正数，同时K--
            if (nums[i] < 0 && K > 0) {
                nums[i] = -nums[i];
                K--;
            }
        }
        // 如果K还大于0，那么反复转变数值最小的元素，将K用完

        if (K % 2 == 1){
            nums[len - 1] = -nums[len - 1];
        }
        return Arrays.stream(nums).sum();

    }
    /*0.贪心算法--将数组全都变为整数，再根据k的值减去最小数*/
    @Test
    public void T_0() {
        int[][] nums = {{-4, -3, -2}, {-8, 3, -5, -3, -5, -2}, {4, 2, 3}, {3, -1, 0, 2}, {2, -3, -1, 5, -4}};
        int[] n2 = {4, 6, 1, 3, 2};
        int[] ans = {5, 22, 5, 6, 13};
        for (int i = 0; i < nums.length; i++) {
            System.out.println(largestSumAfterKNegations(nums[i], n2[i]) == ans[i]);
        }
    }

    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int sum = 0, fIndex = 0;
        while (fIndex <= nums.length - 1 && nums[fIndex] < 0 && k > 0) {
            nums[fIndex] = -nums[fIndex];
            k--;
            fIndex++;
        }
        for (int num : nums) {
            sum += num;
        }

        if (k % 2 == 1) {
            if (fIndex == nums.length) {
                sum -= 2 * nums[fIndex - 1];
            } else if (fIndex == 0) {
                sum -= 2 * nums[fIndex];
            } else {
                sum -= 2 * Math.min(nums[fIndex - 1], nums[fIndex]);
            }
        }
        return sum;
    }

    @Test
    public void T_sumFunc(){
        int []nums = {1,2,3};
        int ans = Arrays.stream(nums).sum();
        System.out.println(ans);
    }
}
